package com.leetcode.midium;

/**
 * @author zfl
 * @Classname MaxArea
 * @Description 盛最多水的容器
 * @Date 2020/10/12 15:21
 */
public class MaxArea {

    /**
     * @param height
     * @return
     * 暴力法
     * 执行用时：1058 ms, 在所有 Java 提交中击败了5.04%的用户
     * 内存消耗：40.1 MB, 在所有 Java 提交中击败了7.53%的用户
     */
    public static int maxArea1(int[] height) {
        if(height.length < 2) {
            return 0;
        }
        int max = 0;
        for (int i = 0; i < height.length - 1; i++) {
            for (int j = i + 1; j < height.length; j++) {
                max = Math.max(max,(j - i) * (height[j] > height[i] ? height[i] : height[j]));
            }
        }
        return max;
    }

    /**
     * @param height
     * @return
     * 双指针法：左右两个指针，每次移动值比较小的指针
     * 执行用时：4 ms, 在所有 Java 提交中击败了67.99%的用户
     * 内存消耗：40.4 MB, 在所有 Java 提交中击败了6.19%的用户
     */
    public static int maxArea2(int[] height) {
        if(height.length < 2) {
            return 0;
        }
        int max = 0;
        int left = 0, right = height.length - 1;
        while (left < right) {
            max = Math.max(max, (right - left) * (height[right] > height[left] ? height[left] : height[right]));
            if (height[right] > height[left]) {
                left++;
            } else {
                right--;
            }
        }
        return max;
    }
}
